package net.cloudsun.tree.binary;

import net.cloudsun.tree.Node;
import net.cloudsun.tree.util.CharArrayUtils;

import java.util.*;
import java.util.function.Consumer;
import java.util.function.Predicate;

/**
 * @author Ryan
 * @since
 */
public abstract class BinaryNode<T> implements Node<T> {

    private static final int MAX_SIZE = 2;
    // 非静态字段
    protected BinaryNode<T> parent;
    private BinaryNode<T> left;
    private BinaryNode<T> right;
    protected T value;
    /**
     * 高度，避免实时计算
     */
    protected int height = 1;


    public BinaryNode(T t) {
        this.value = t;
    }

    /**
     * 宽度搜索
     *
     * @param visitor
     */
    public void bfs(Predicate<Node<T>> visitor) {
        final Deque<BinaryNode<T>> nodes = new ArrayDeque<>();
        nodes.add(this);
        while (!nodes.isEmpty()) {
            BinaryNode<T> node = nodes.pop();
            nodes.addAll(node.getChildren());
            if (!visitor.test(node)) {
                break;
            }
        }
    }

    /**
     * 深度搜索
     *
     * @param visitor
     */
    public void dfs(Predicate<Node<T>> visitor) {
        final Deque<BinaryNode<T>> nodes = new ArrayDeque<>();

        nodes.add(this);
        while (!nodes.isEmpty()) {
            BinaryNode<T> node = nodes.pop();
            List<BinaryNode<T>> children = node.getChildren();
            Collections.reverse(children);
            children.forEach(nodes::push);
            if (!visitor.test(node)) {
                break;
            }
        }
    }

    @Override
    public T getValue() {
        return value;
    }

    public void setValue(T value) {
        this.value = value;
    }

    @Override
    public BinaryNode<T> getParent() {
        return parent;
    }

    @Override
    public List<BinaryNode<T>> getChildren() {
        final ArrayList<BinaryNode<T>> objects = new ArrayList<>(MAX_SIZE);
        if (left != null) {
            objects.add(left);
        }
        if (right!=null) {
            objects.add(right);
        }
        return objects;
    }

    public BinaryNode<T> getLeft() {
        return left;
    }

    public BinaryNode<T> getRight() {
        return right;
    }

    public void setLeft(BinaryNode<T> left) {
        this.left = left;
        if (left != null) {
            left.parent =  this;
        }
        adjustHeight();
    }

    public void setRight(BinaryNode<T> right) {
        this.right = right;
        if (right != null) {
            right.parent = this;
        }
        adjustHeight();
    }

    public void setParent(BinaryNode<T> parent) {
        this.parent = parent;
    }

    public boolean isFull() {
        return left != null && right != null;
    }

    public boolean isEmpty() {
        return left == null && right == null;
    }

    public abstract void add(BinaryNode<T> newNode);

    public int getHeight() {
        return height;
    }

    public boolean isLeftChild() {
        return parent != null && this == parent.left;
    }

    public boolean isRightChild() {
        return parent != null && this == parent.right;
    }

    public void removeChild(BinaryNode<T> child) {
        child.parent = null;
        if (child == left) {
            setLeft(null);
        } else if (child == right) {
            setRight(null);
        }
    }

    @Override
    public String toString() {
        return value.toString();
    }


    private void adjustHeight() {
        int originHeight = height;
        // 调整高度
        int leftHeight = 0;
        int rightHeight = 0;
        if (left != null) {
            leftHeight = left.height;
        }
        if (right != null) {
            rightHeight = right.height;
        }
        height = Math.max(leftHeight, rightHeight) + 1;
        if (height != originHeight) {
            // 发生变化之后要往上处理
            for(BinaryNode<T> pointer = this;pointer!=null;pointer = pointer.parent) {
                pointer.adjustHeight();
            }

        }
    }

    /**
     * bfs
     * @param visitor
     */
    public void forEach(Consumer<Node<T>> visitor) {
        bfs(x-> {
            visitor.accept(x);
            return true;
        });
    }

    /**
     * @return 构建一个字符串
     */
    public String toTreeString() {

        final HashMap<BinaryNode<T>, NodeString<T>> map = new HashMap<>();

        NodeString[] prevValue = new NodeString[1];
        forEach(tNode -> {
            final NodeString nodeString = new NodeString<>((BinaryNode<T>) tNode, map, prevValue[0]);
            map.put((BinaryNode<T>) tNode, nodeString);
            prevValue[0] = nodeString;
        });
        Optional<Integer> maxX = map.entrySet().stream().map(e-> e.getValue().getMaxX()).max(Integer::compareTo);
        Optional<Integer> minX = map.entrySet().stream().map(e-> e.getValue().x).min(Integer::compareTo);
        // 调整前的map
        map.forEach((k,v)-> v.x += -minX.get());

        // 构建一个字符串矩阵 maxX - minX + 1
        char[][] chars = CharArrayUtils.getCharMatrix(map, maxX.orElse(0) - minX.orElse(0), this.height);
        return CharArrayUtils.joinCharMatrix(chars);
    }

    protected BinaryNode<T> getSibling() {
        if (parent == null) {
            return null;
        }
        if (parent.left == this) {
            return parent.right;
        }

        return parent.left;
    }
}
